package org.example.sword2offer.primary;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:手写hashmap  https://www.bilibili.com/video/BV1Qz4y1C7vk?p=6
 * @date: 2021/7/27 22:08
 */

import java.util.ArrayList;
import java.util.List;

/**
 1. 技术的本质
 存储key和value
 存储> 数据结构和算法
 hashmap的数据结构： JDK7 数组和链表；JDK8:数组，链表，红黑树
 数组底层是arraylist和linkedlist
 算法： hash算法

 写法顺序: put(hash,),get,
 */
public class Q90_MyHashMap<K,V> implements Q90_Map<K,V> {
    private Entry<K,V> table[];
    int size=0;
    private int defaultLength;//默认长度
    private double defaultAddFactor;//默认负载因子
    public Q90_MyHashMap() {
        this(16, 0.75);
    }
    public Q90_MyHashMap(int defaultLength, double defaultAddFactor){
        if (defaultLength < 0) {
            throw new IllegalArgumentException("数组异常");
        }
        if (defaultAddFactor <= 0 || Double.isNaN(defaultAddFactor)) {
            throw new IllegalArgumentException("因子异常");
        }
        this.defaultLength = defaultLength;
        this.defaultAddFactor = defaultAddFactor;
        table=new Entry[defaultLength];
    }

    /**
     *
     * @param k
     * @param v
     * @return
     */
    @Override
    public V put(K k, V v) {
        if (size > defaultAddFactor * defaultLength) {
            //扩容
            resize();
        }

        int index=getIndex(k,table.length);
        //ctrl + alt + v 补全返回值
        Entry<K, V> kvEntry = table[index];
        if (kvEntry==null){
            table[index]=new Entry<>(k,v,index,null);
            size++;
        }else {
            //如果有值得话，就将kvEntry用尾插法插入到后面
            table[index]=new Entry<>(k,v,index,kvEntry);
        }
        return table[index].getValue();
    }
    private int getIndex(K k,int length){
        int m=length-1;
        int index=k.hashCode()%m;
        return index<0?-index:index;
    }
    //fixme 扩容,导致cpu % 的原因，1.7头插法 https://www.bilibili.com/video/BV13y4y1u7yV?p=6
    private void resize() {
        Entry<K, V>[] newTable = new Entry[defaultLength * 2];
        List<Entry<K, V>> list = new ArrayList<>();
        for (int i = 0; i < table.length; i++) {
            if (table[i] == null)
                continue;
            //遍历链表 添加到list
            Entry<K, V> entry = table[i];
            while (entry != null) {
                list.add(entry);
                entry = entry.next;
            }
        }
        if (list.size() > 0) {
            size = 0;
            defaultLength = defaultLength * 2;
            table = newTable;
            for (Entry<K, V> entry : list) {
                //分离所有的entry
                if (entry.next != null) {
                    entry.next = null;
                }
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    //fixme https://www.zhihu.com/question/20733617
    private int hash(K k){
        int h;
        return (k == null) ? 0 : (h = k.hashCode()) ^ (h >>> 16);
    }




    @Override
    public V get(K k) {
        if (size==0) return null;
        int index = getIndex(k,table.length);
        Entry<K,V> entry=findValue(table[index],k);
        return entry==null?null:entry.getValue();
    }

    //采用递归的方式实现
    private Entry<K,V> findValue(Entry<K,V> entry, K k) {
        if (k.equals(entry.getKey())||k==entry.getKey()){ //复杂类型的==还不行
            return entry;
        }else {
            if (entry.next!=null){
                return findValue(entry.next,k);
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    //这个就是链表
    class Entry<K,V> implements Q90_Map.Entry<K,V> {
        K k;V v; int hash;Entry<K,V> next;
        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }
        @Override
        public K getKey() {
            return k;
        }
        @Override
        public V getValue() {
            return v;
        }
    }

    public static void main(String[] args) {
        Q90_Map<String,Object> map=new Q90_MyHashMap<>(8,0.5);
        map.put("1",23);
        map.put("2",34);
        map.put("3",45);
        map.put("4",56);
        map.put("5",67);
        map.put("6",78);
        System.out.println(map.get("1"));
        System.out.println(map.get("2"));
    }
}
